perm filename WINGED.DOC[1,BGB] blob sn#001276 filedate 1972-10-28 generic text, type T, neo UTF8
00100	STANFORD ARTIFICIAL INTELLIGENCE PROJECT                 OCTOBER 1972
00200	MEMO AIM-XXX
00300	
00400	COMPUTER SCIENCE DEPARTMENT REPORT
00500	NO. CS-XXX
00600	
00700	
00800	
00900	               WINGED EDGE POLYHEDRON REPRESENTATION.      
01000	            
01100	                          Bruce G. Baumgart      
01200	           
01300	
01400	Abstract:	A winged edge polyhedron representation is stated and
01500	a  set  of  primitives  that  preserve Euler's F-E+V = 2 equation are
01600	explained.     Present  use  of  this  representation  in  Artificial
01700	Intelligence  for computer graphics and world modeling is illustrated
01800	and its intended future application to computer vision is discribed.
01900	
02000	
02100	CONTENTS
02200	
02300		I.   INTRODUCTION.
02400			A. Introduction to World Modeling.
02500			B. Introduction to a Camera Model.
02600			C. Introduction to Body, Face, Edge, Vertex Modeling.
02700	
02800		II.  DATA STRUCTURE of Winged Edge Polyhedra.
02900			A. Winged Edge Structure.
03000			B. Winged Edge Operations.
03100			C. Elaborations.
03200	
03300		III. PRIMITIVES on Polyhedra.
03400			A. Euler Primitives.
03500			B. Solid Primitives.
03600			C. Geometric Primitives.
03700			D. Image Forming Primitives.
03800	
03900		IV.  APPLICATIONS.
04000			A. Modeling: GEOMED - a 3D drawing editor.
04100			B. Graphics: OCCULT - a hidden line eliminator.
04200			C. Vision:   CAREYE - a video region-edge finder.
04300	
04400	This research was supported in part by the Advanced Research Projects
04500	Agency  of  the  Office  of  the  Secretary of Defence under contract
04600	SD-183.
     

00100	FIGURE 1.1  -  Example World Model Scenes.
00200		1a. A parking lot scene.
00300		1b. The hand-eye table, arm, camera, and some blocks.
     

00100	I. INTRODUCTION.
00200	
00300		In order to get a computer to deal with the physical world it
00400	must  have  a  data  representation  on  which computations involving
00500	space, time, shape, size, and the appearance of things can  be  done.
00600	It is my current prejudice that polyhedra provide the proper starting
00700	point for building such a physical world representation.  At Stanford
00800	Artificial  Intelligence,  Binford and Agin have started instead with
00900	spine-cross section models as  an  alternate  approach  to  the  same
01000	problems  [reference 1].    Other researchers with somewhat different
01100	goals, are attempting to build semantic, predicate calculus,  problem
01200	solving,  or  startegy  planning  world models.    In any event, this
01300	paper is about a body, face, edge, vertex polyhedron  model  that  is
01400	for  modeling  objects and scenes of objects for the sake of computer
01500	vision.
01600	
01700		Although the data structure to be discussed is  not  language
01800	dependent,  the  terminlogy  and examples will follow ALGOL and LISP.
01900	Also, the reader is assumed to have some acquaintance with the  ideas
02000	associated with the following technical terms:
02100	
02200		A: block, node, item, element, atom.
02300		B: link, pointer, address, reference.
02400		C: datum, content, value.
02500		D: list, ring, stack, pdl, tree.
02600		E: dynamic free storage & memory allocation.
02700	
02800	A  thorough  presentation  of  these  terms and ideas can be found in
02900	chapter two of volume one of Knuth's cookbook, `The Art  of  Computer
03000	Programming'  [Reference 7].  The word "ring" used informally in this
03100	paper will always mean a double pointer ring with a head; and  as  in
03200	LISP, words of memory happen to be able to hold two pointers.
03300	
03400		Finally, the reader should be warned that the
03500	advantages of using a winged edge polyhedron representation
03600	rather than some other representation are not explicitly documented
03700	in this paper. To formally demonstrate the advantage of
03750	one representation over another would require running bench mark
03850	problems on implementations of the representations in the same
03950	language and the same environment.
04050	However on an informal testimonial level, I feel the winged edge
04150	representation
     

00100	FIGURE 1.2  -  A Polyhedron Model of a Mechanical Arm.
     

00100	I. A. Introduction to World Modeling.
00200	
00300		I  will introduce my requirements for a computer model of the
00400	physical world in terms of its role as a memory.    As  a  memory,  a
00500	world  model  has  contents and an addressing mechanism. The kinds of
00600	data that I wish to hold in my world model are:
00700	
00800		CONTENT REQUIREMENTS
00900			1. Topological data.
01000			2. Geometric data.
01100			3. Photometric data.
01200			4. Parts tree data.
01300	
01400		Topological data has to do with the notion of neighborhood; a
01500	world model has data on what is next to what. A  face,  edge,  vertex
01600	model is essentially dedicated to surface topology; matters of volume
01700	topology are not stored but rather must be computed.  Geometric  data
01800	has  to  do  with  notions  such  as  locus, length, area and volume.
01900	Photometric data includes the locus and nature of light  sources,  as
02000	well as data on how surfaces reflect, absorb and scatter light. Parts
02100	tree data has to do with the notion  that  objects  are  composed  of
02200	parts,  which  I  construe  as  data on the structure of the physical
02300	world rather than as purely an artifact of  having  structured  world
02400	data; that is, I prefer to have the specification of how an entity is
02500	broken into parts be external to my world model. The  kinds  of  data
02600	not included are semantic data (other than body names); physical data
02700	such as mass, inertia tensors, electrical properties and so  on;  and
02800	cultural  data  such  as whether an object is a toy, tool, or weapon;
02900	with any artistic, religious or market value.
03000	
03100		Next  the  kinds of addressing mechanisms I wish to have, (or
03200	equivalently the input-output modes of the model) are:
03300	
03400		ACCESSING REQUIREMENTS
03500			1. Appearance - given a camera,  return an image of 
03600			   what the world would look like from that camera.
03700			2. Recognition - given an image, return the objects
03800			   from the world model  that appear in that image.
03900			3. Camera Solution  -  given  a  recognized  image,
04000			   find  the  location & orientation of the camera.
04100			4. Perception - given images,  from solved cameras,
04200			   place new bodies  into the model for portions of
04300			   the images  that  have not  yet been recognized.
04400			5. Spatial Accessing  -  given a locus  and radius,
04500			   return the portions  of objects  in that sphere.
04600	
04700	Clearly,  these  are  the high level accessing requirements which are
04800	the reasons for having a world model and the design goals  for  model
04900	building.
     

00100	FIGURE 1.3  -  A Camera Model.
00200	
00300	FIGURE 1.4  -  Logical & Physical Raster Sizes.
     

00100	I. B. Introduction to a Camera Model.
00200	
00300		As the accessing requirements imply, a world model requires a
00400	special  entity  called  a  camera  which  is  used  to  model  image
00500	formation. Although the camera model is important here for a complete
00600	specification  of the data, it may be skipped on a first reading. The
00700	particular camera model I have been using  lately,  is  expressed  by
00800	eighteen  real numbers involving nine degrees of freedom. First there
00900	is the camera lens center locus:
01000	
01100			CX, CY, CZ,	in world coordinates.
01200	
01300	Afixed to the lens center is the camera frame of reference with  unit
01400	vectors  i, j and k. When the image formed by the camera is placed in
01500	correspondence to a display screen, as illustrated in figure 1.3, the
01600	unit  vector  i  maps  into  the  rightward positive x of the display
01700	screen, and the unit vector j maps into the upward positive y of  the
01800	display screen, and the unit vector k comes out of the display screen
01900	to form a right handed coordinate system.  Together  the  three  unit
02000	vectors of the camera are the three by three rotation matrix:
02100	
02200			IX, IY, IZ
02300			JX, JY, JZ	in world coordinates.
02400			KX, KY, KZ
02500	
02600	Next,  there  are  three  scales  which  determine the correspondence
02700	between world size and image size. Observe that the world is measured
02800	in physical units of length like meters or feet while computer images
02900	come in integral sizes like 1024 by 1024 or 480 rows by 512  columns,
03000	thus  the  conversion  scales must be in terms of logical image units
03100	per physical world units.   In an actual television camera  a  minute
03200	image  (say  9mm  by 12mm) is formed on a vidicon tube and that image
03300	has a particular number of rows and columns. It is the  little  image
03400	on the vidicon that we pretend to model by the six parameters:
03500	
03600			LDX, LDY, LDZ		Logical raster size.
03700			PDX, PDY, FOCAL		Physical raster size.
03800	
03900	Where the number named FOCAL, is the focal plane  distance  which  in
04000	this model (with distant objects) can safely be equated with the lens
04100	focal length and can be given in millimeters (conventional  lens  run
04200	12.5mm  to  75mm for 1" TV).   The integer LDZ is an artifact so that
04300	the units come out correctly in the  Z  dimension.  Thus  the  scales
04400	factors are defined:
04500	
04600			SCALEX ← -FOCAL*LDX/PDX;
04700			SCALEY ← -FOCAL*LDY/PDY;
04800			SCALEZ ←  FOCAL*LDZ;
04900	
05000		This  simple  camera  model  is  used to compute vertex image
05100	coordinates.   A more elaborate physical camera model can be found in
05200	Sobel [reference 9].
     

00100	FIGURE 1.5 	Renaissance man looking at a cube.
     

00100	I. C. Introduction to Body, Face, Edge, Vertex (BFEV) Modeling.
00200	
00300		This introduction to  BFEV  modeling  will  be  informal  and
00400	specific to the winged edge model presented in part-II of this paper.
00500	Many  of  the  basic  numerical  relations  which  make  BFEV  models
00600	important are stated in ALGOL notation without proof.
00700	
00800	The Vertex.
00900	
01000		A  vertex  is  an  instance  of  a point in a Euclidean three
01100	space.   The important thing about a vertex is its world locus  (with
01200	component names XWC,YWC,ZWC standing for world-coordinates).   Vertex
01300	locii are the basic geometric data  from which length, area,  volume,
01400	face  vectors  and image positions can be computed. Also a Vertex may
01500	exist simultaneously in one or more  image  spaces.  An  image  space
01600	(with component names XPP,YPP,ZPP standing for perspective-projected)
01700	is always three dimensional and is determined with respect to a given
01800	camera  centered  coordinate system (with component names XCC,YCC,ZCC
01900	standing for camera-coordinates).    The third image component,  ZPP,
02000	is  taken  inversely  proportional to the distance of the vertex from
02100	the camera image  plane,  ZCC.  Using  the  camera  of  the  previous
02200	section.  The  transformation  of  a  vertex  world locus to a camera
02300	centered locus is:
02400	
02500				X ← XWC - CX;
02600				Y ← YWC - CY;
02700				Z ← ZWC - CZ;
02800	
02900				XCC ← IX*X + IY*Y + IZ*Z;
03000				YCC ← JX*X + JY*Y + JZ*Z;
03100				ZCC ← KX*X + KY*Y + KZ*Z;
03200	
03300		The first three assignment statements are the translation  to
03400	the  camera  frame's origin,  the  second  three  assignments are the
03500	rotation to the camera frame's orientation.    Next  the  perspective
03600	projection transformation is computed:
03700	
03800				XPP ←  SCALEX*XCC/ZCC;
03900				YPP ←  SCALEY*YCC/ZCC;
04000				ZPP ←  SCALEZ    /ZCC;
04100	
04200		The XPP and YPP assignments are derived by means  of  similar
04300	triangles,  as  is  being  done  by  the  man  in figure 1.5; the Zpp
04400	assignment  is  for  preserving  the  depth   information   and   the
04500	colinearity of the world in the perspective projected image space. As
04600	given, the PP frame is right handed and  vertices  in  front  of  the
04700	camera's  image  plane will have negative Zpp; Zpp values near -FOCAL
04800	are close to the camera and values approaching zero are far away.
04900	
05000		A final matter with respect to vertices is their valence. The
05100	valence of a vertex is the number of edges that meet at the vertex. A
05200	vertex valence of three, for example, indicates a trihedral corner.
     

00100	I. C. Introduction to BFEV Modeling. (continued).
00200	
00300	The Edge.
00400	
00500		For  a  start, the structure of an edge need be thought of as
00600	little more than two vertices; the topological subtlety of edges will
00700	be  explained  later.  However,  two vertices do define the important
00800	geometric edge data called the 2D line coefficients.  Named  AA,  BB,
00900	CC; these coefficients are computed from the perspective locus of the
01000	edge's endpoints as follows:
01100	
01200	                        AA ← Y1 - Y2;
01300	                        BB ← X2 - X1;
01400	                        CC ← X1*Y2 - X2*Y1;
01500	
01600	These coefficients appear  in  the  2D  equation  of  the  line  that
01700	contains the edge:
01800				0 = AA*X + BB*Y + CC;
01900	
02000	When the edge coefficients are normalized:
02100	
02200				L   ← SQRT(AA↑2+BB↑2);
02300				AA  ← AA/L;
02400				BB  ← BB/L;
02500				CC  ← CC/L;
02600	
02700	the line equation gives the distance, of a point X,Y from the line:
02800	
02900				Q ← AA*X + BB*Y + CC;
03000	
03100	The distance is actually ABS(Q), since Q is negative on one side side
03200	of  the  line;  also if one were standing on the plane at point X1,Y1
03300	facing X2,Y2 the Q positive half-plane would be on your left and  the
03400	Q negative half plane would be on your right.
03500	
03600		An  important  operation on two edges is to detect whether or
03700	not they intersect; this can be decided by checking first whether the
03800	endpoints  of  one  edge are in the opposite half planes of the other
03900	edge, and second whether the endpoints of the latter edge are in  the
04000	opposite half planes of the first.  When both conditions obtain, then
04100	the intersection point can be found:
04200	
04300				T ← (A1*B2 - A2*B1);
04400				X ← (B1*C2 - B2*C1)/T;
04500				Y ← (A2*C1 - A1*C2)/T;
04600	
04700	An  actual  compare  for  intersection should initially check for the
04800	identity case, and for edges with a vertex in common.
     

00100	I. C. Introduction to BFEV Modeling. (continued).
00200	
00300	The Face.
00400	
00500		A face is a finite  region  of  plane  enclosed  by  straight
00600	lines.   A  safe  formal  face structure could be built by defining a
00700	triangle as three non-colinear vertices and then insisting  that  all
00800	faces  be  triangle  interiors.   Unhappily,  BFEV  faces are usually
00900	represented as a list of vertices and edges (or by  something  nearly
01000	equivalent)  for  the sake of saving memory space.  Such `list' faces
01100	are not monolithic but tend to suffer special cases  and  pathologies
01200	such as:
01300			Coincident or crossing edges,
01400			Holes and Disjointness,
01500			Concavity (& Convexity),
01600			Non-coplanarity.
01700	
01800	Like edges, faces have characteristic coefficients. Face coefficients
01900	satisfy the equation of a plane in which the face is embedded:
02000	
02100		AA*X + BB*Y + CC*ZZ = KK.
02200	
02300	The equation could be divided by KK, but that is undesirable  because
02400	the AA, BB, CC are more useful as a unit normal vector, in which case
02500	KK is the distance of the origin from the plane.  Given the locii  of
02600	three  non-colinear  vertices, the  coefficients  of  a  plane can be
02700	computed by Kramer's rule as follows:
02800	
02900		KK    ←   X1*(Z2*Y3-Y2*Z3) 
03000			+ Y1*(X2*Z3-Z2*X3) 
03100			+ Z1*(Y2*X3-X2*Y3);
03200		AA    ← (Z1*(Y2-Y3) + Z2*(Y3-Y1) + Z3*(Y1-Y2));
03300		BB    ← (X1*(Z2-Z3) + X2*(Z3-Z1) + X3*(Z1-Z2));
03400		CC    ← (X1*(Y3-Y2) + X2*(Y1-Y3) + X3*(Y2-Y1));
03500	
03600	and normalized:
03700	
03800		ABC ← SQRT(AA↑2 + BB↑2 + CC↑2);
03900		AA  ← AA/ABC;
04000		BB  ← BB/ABC;
04100		CC  ← CC/ABC;
04200		KK  ← KK/ABC;
04300		
04400	If  the  given  vertices  V1,  V2,  V3  had  been taken going counter
04500	clockwise about the face as viewed from the exterior  of  the  solid,
04600	then the following relations obtain:
04700	
04800		AA*X + BB*Y + CC*Z > KK implies X,Y,Z above the plane.
04900		AA*X + BB*Y + CC*Z = KK implies X,Y,Z in the plane.
05000		AA*X + BB*Y + CC*Z < KK implies X,Y,Z below the plane.
05100	
05200	Face coefficients prove useful in both world and image coordinates.
     

00100	(blank page)
     

00100	I. C. Introduction to BFEV Modeling. (continued).
00200	
00300	POLYHEDRA, BODIES and OBJECTS.
00400	
00500		In  elementary  geometry,  a polyhedron is said to be a solid
00600	formed (or bounded) by plane faces; the word  "polyhedron"  literally
00700	meaning  "many-faced".      Topologically,  simple  polyhedra satisfy
00800	Euler's F-E+V=2 equation; where F, E and V are the number  of  faces,
00900	edges  and vertices of the polyhedron respectively. This equation was
01000	known to Descartes in 1640, but the first proof  wasn't  given  until
01100	1752,  when  Euler  proved  the  relation  by  considering  the graph
01200	corresponding to the edges of polyhedra.  A simple polyhedron is  one
01300	homeomorphic to a sphere. The rigorous development of volume measure,
01400	and in turn `solid' polyhedra, is not simple; thus it has been easier
01500	to  take  the  topological  notion  F-E+V=2  as  the  more  primitive
01600	definition of a polyhedron on which to base a data structure  and  to
01700	proceed  towards  the  appearance  of  `solidness'  which  is  a more
01800	complicated notion.
01900	
02000		Counter to the usual usuage, I define the word "body" to mean
02100	an  entity  more  specific  than  a polyhedron; the idea being that a
02200	polyhedron is represented by the whole structure  of  bodies,  faces,
02300	edges  and vertices. Bodies may have location, orientation and volume
02400	in space. Bodies may be conected to faces, edges and vertices,  which
02500	may  or  may  not  form a complete polyhedron.  It is typical to have
02600	only one body to a polyhedron when representing a rigid object like a
02700	sledge  hammer and several bodies to a polyhedron when representing a
02800	flexible object like a man. Furthermore, the body concept is used  to
02900	handle  the  notion  of parts and abstract regional objects such as a
03000	parking  lot.      For  example,  the  Stanford  AI  Parking  Lot  is
03100	represented  by  a  body that has three parts:  the Near, Mid and Far
03200	Lots. The Near Lot then has aisles and lanes and lamp islands; a lamp
03300	island  has  a  curb  and two lamps; a lamp has a base, stem and top.
03400	This parts structure is carried in body nodes.    Finally,  the  word
03500	"object"  will  be  used  to  refer  to  physical  objects  such as a
03600	redwood-tree, building, or roadway.
     

00100	Figure 1.6
00200	FACE PERIMETER - a face is surrounded by edges and vertices.
00300	
00400	                     VERTEX  
00500			        ⊗
00600			       / \
00700	                      /   \
00800	                     /     \
00900	                    /       \
01000	             EDGE  /         \  EDGE
01100	                  /           \
01200	                 /    FACE     \
01300	                /               \
01400	               /                 \
01500	              /                   \
01600	      VERTEX ⊗---------------------⊗ VERTEX
01700			      EDGE
01800	
01900	Figure 1.7
02000	VERTEX PERIMETER - a vertex is surrounded by edges and faces.
02100	
02200			      EDGE
02300				|
02400				|
02500		      FACE	|      FACE
02600				|
02700				⊗ VERTEX
02800		               / \
02900		              /   \
03000		             /     \
03100		            /       \
03200			   /  FACE   \
03300		       EDGE    	      EDGE
03400	
03500	Figure 1.8
03600	EDGE PERIMETER - an edge is surrounded by 2 faces & 2 vertices.
03700	
03800			     VERTEX
03900	
04000				⊗
04100				|
04200				|
04300			FACE	E    FACE
04400				|
04500				|
04600				⊗
04700			
04800			     VERTEX
     

00100	I. C. Introduction to BFEV Modeling. (continued).
00200	
00300	FOUR KINDS OF BFEV ACCESSING.
00400	
00500		1. Accessing by name and serial number.
00600		2. Parts-Tree Accessing.
00700		3. FEV Sequential Accessing.
00800		4. FEV Perimeter Accessing.
00900	
01000		A   BFEV  model  has  four  kinds  of  accessing.   The  most
01100	conventional BFEV access is retrieval by symbolic name which requires
01200	a  symbol  table. Next, between bodies there is Parts-Tree accessing.
01300	At the top of the Parts-Tree is a special body  named  the  world  to
01400	which  all  the other bodies are attached; thus the world body serves
01500	as an OBLIST node. Given a particular body, a list of  its  sub-parts
01600	can  be  retrieved as well as its supra-part or "supart". A supart is
01700	the whole entity to which a part belongs, the  world  being  its  own
01800	supart.
01900	
02000		Within  each  body  there is face, edge and vertex sequential
02100	accessing. Given a body, all its faces, or edges, or vertices need to
02200	be  readily available since perspective projection loops thru all the
02300	vertices, and the process of display  clipping  loops  thru  all  the
02400	edges,  and  the act of checking for body intersection loops thru all
02500	the faces. In LISP, one might provide  FEV  sequential  accessing  by
02600	placing  a  list  of faces, a list of edges and a list of vertices on
02700	the property list of each body, so that a cube might  be  represented
02800	as:
02900	
03000		(DEFPROP CUBE (F1 F2 F3 F4 F5 F6) FACES)
03100		(DEFPROP CUBE (E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12)EDGES)
03200		(DEFPROP CUBE (V1 V2 V3 V4 V5 V6 V7 V8) VERTICES)
03300	
03400		Finally,  among the faces, edges and vertices of a body there
03500	is perimeter accessing. Faces have a perimeter of edges and  vertices
03600	[figure  1.6]; less commonly used, vertices have a perimeter of edges
03700	and faces  [figure  1.7];  and  of  particular  note,  edges  have  a
03800	perimeter  always formed by two faces and two vertices, [figure 1.8].
03900	Perimeter accessing requires that given a face, edge or vertex,  that
04000	the perimeter of that entity be readily accessible. Since the surface
04100	of a polyhedron is orientable, that is has a well defined inside  and
04200	outside,  (Klein  bottles  with their crosscaps will not be modeled),
04300	such perimeter lists can be ordered (say clockwise) with  respect  to
04400	the  exterior  of the polyhedron. Perimeter accessing is mentioned in
04500	Guzman [reference 6] and Falk [reference 4]  and  is  the  underlying
04600	basis  of  part-II  of  this  paper which presents a polyhedron model
04700	built for accessing and altering face, edge and vertex perimeters.
     

     

00100	Figure 2.1 - BASIC NODE STRUCTURE.
00200	
00300	BODY-BLOCK	FACE-BLOCK	EDGE-BLOCK	VERTEX-BLOCK
00400	-3. part,copart	-3.		-3.		-3. XWC
00500	-2.		-2.		-2.		-2. YWC
00600	-1.		-1.		-1.		-1. ZWC
00700	 0. type	 0. type	 0. type	 0. type
00800	+1. nface,pface +1. nface,pface	+1. nface,pface	+1.
00900	+2. ned,ped	+2. ped		+2. ned,ped	+2. ped
01000	+3. nvt,pvt	+3.		+3. nvt,pvt	+3. nvt,pvt
01100	+4.		+4.		+4. ncw,pcw	+4.
01200	+5.		+5.		+5. nccw,pccw	+5.
01300	+6.		+6.		+6.		+6.
01400	    5 words	    2 words	    6 words	    5 words
01500	
01600	
01700	Figure 2.2 - THE WINGED EDGE.
01800		(As viewed from the exterior of a solid).
01900	
02000				\	  /
02100			 NCCW(E) \	 / PCW(E)
02200		                  \     /
02300		                   \   /      
02400		                    \ /
02500		                     ⊗ PVT(E)
02600		                     |
02700	                             | 
02800	               NFACE(E)      E         PFACE(E)
02900		                     |
03000		                     |
03100		              NVT(E) ⊗
03200		                    / \
03300		                   /   \        
03400		                  /     \
03500			  NCW(E) /	 \ PCCW(E)
03600				/	  \
03700	
03800	
03900	
04000	Figure 2.3 - AN ACTUAL NODE STRUCTURE - SEPTEMBER 1972.
04100	
04200	BODY-BLOCK	FACE-BLOCK	EDGE-BLOCK	VERTEX-BLOCK
04300	-3. part,copart	-3. AA		-3. AA		-3. XWC
04400	-2. locor	-2. BB		-2. BB		-2. YWC
04500	-1. pname,	-1. CC		-1. CC		-1. ZWC
04600	 0. type,serial	 0. type,serial	 0. type,serial	 0. type,serial
04700	+1. nface,pface +1. nface,pface	+1. nface,pface	+1. XDC,Tjoint
04800	+2. ned,ped	+2. ped		+2. ned,ped	+2. YDC,ped
04900	+3. nvt,pvt	+3. QQ		+3. nvt,pvt	+3. nvt,pvt
05000	+4. Fcnt,Vcnt	+4. KK		+4. ncw,pcw	+4. XPP
05100	+5. Ecnt,Pcnt	+5. 		+5. nccw,pccw	+5. YPP
05200	+6. nbody,pbody	+6. alt,	+6. alt,pbody	+6. Zpp
     

00100	PART-II. THE WINGED EDGE DATA STRUCTURE.
00200		
00300	
00400	II. A. Winged Edge Data Structure.
00500	
00600		Bodies, Faces, Edges and Vertices are represented  by  blocks
00700	of  contiguously addressed words. A single block size of ten words is
00800	adequate. A single word, like a LISP node, can hold two addresses  or
00900	a  floating  point  number.  The  BFEV  blocks  are pointed at by the
01000	address of their word  numbered  zero  which  contains  control  bits
01100	indicating  whether the block is a body, face, edge or vertex. Figure
01200	2.1 illustrates the block  format  that  is  being  presented  as  an
01300	example  of  a  winged edge data structure; a minimal number of words
01400	for each block is indicated.
01500	
01600		The  basic  geometric  datum  is  the  vertex locus, which is
01700	stored in three words of each vertex block at positions -3,  -2,  -1;
01800	these  positions  are  named  XWC, YWC, ZWC respectively; the letters
01900	"WC" standing for "world coordinates".
02000	
02100		The basic topological data are the three rings of  the  body;
02200	(a  ring  of  faces, a ring of edges, and a ring of vertices) and the
02300	winged edge pointers (eight such pointers in each edge block,and  one
02400	such  pointer  in  each  face  and  vertex block). The face, edge and
02500	vertex ring pointers  are  stored  at  positions  +1,  +2,  +3;  each
02600	position  has  two  names:    NFACE,  NED,  NVT for the left pointers
02700	respectively; and PFACE, PED, PVT for the right.   A  face,  edge  or
02800	vertex can only belong to one body and so there is only one body node
02900	in a given face, edge or vertex ring; and that body  node  serves  as
03000	the  head of the ring. The reason for double pointer rings is for the
03100	sake of rapid deletion; other minor advantages would not justify  the
03200	use of double rings.
03300	
03400		The  eight  WINGED  pointers  of  an edge block include:  two
03500	pointers to the faces of that edge, two pointers to the  vertices  of
03600	that  edge, and four pointers to the next edges clockwise and counter
03700	clockwise in each of that edge's two faces; these last four  pointers
03800	are  called  the  wings of that edge. As figure 2.2 suggests, four of
03900	these eight pointers are stored in the same positions and referred to
04000	by  the  same  names as the face and vertex ring pointers; namely the
04100	NFACE, PFACE, NVT and PVT pointers. There are four ways  in  which  a
04200	pair  of faces and a pair of vertices can be placed into the two face
04300	positions and two vertex positions of an edge; by constraining  these
04400	choices  two  bits are implicitly encoded, one bit is called the edge
04500	parity, and the other is called the surface parity;  these  bits  are
04600	explained  later.  Finally,  the  single winged edge pointer found in
04700	faces and vertices is kept in the position named PED and it points to
04800	one of the edges belonging to that face or vertex.
04900	
05000		Although  the  vertices  in  figure  2.2 are shown with three
05100	edges, vertices may have any number of edges; those  other  potential
05200	edges would not be directly connected to E and so were not shown.
     

00100	A SUMMARY OF WINGED EDGE OPERATIONS.
00200	
00300	
00400	   DYNAMIC STORAGE ALLOCATION.
00500	
00600	1.	Q ← GETBLK(SIZE);
00700	2	RELBLK(Q,SIZE);
00800	
00900	
01000	   BFEV MAKE & KILL OPERATIONS.
01100	
01200	1.	BNEW ← MKB(B);	 KLB(BNEW);
01300	2.	FNEW ← MKF(B);	 KLF(B,FNEW);
01400	3.	ENEW ← MKE(B);	 KLE(B,ENEW);
01500	4.	VNEW ← MKV(B);	 KLV(B,VNEW);
01600	
01700	
01800	   FETCH LINK AND STORE LINK OPERATIONS.
01900	
02000	1.	F ← NFACE(Q); F ← PFACE(Q);  NFACE.(F,Q); PFACE.(F,Q);
02100	2.	E ← NED(Q);   E ← NED(Q);    NED.(E,Q);   PED.(E,Q);
02200	3.	V ← NVT(Q);   V ← NVT(Q);    NVT.(V,Q);   PVT.(V,Q);
02300	4.	A ← NCW(E);   A ← PCW(E);    NCW.(A,E);   PCW.(A,E);
02400	5.	A ← NCCW(E);  A ← PCCW(E);   NCCW.(A,E);  PCCW.(A,E);
02500	
02600	
02700	   WING LINK OPERATIONS.
02800	
02900	1.	WING(E1,E2);
03000	2.	INVERT(E);
03100	
03200	
03300	   PERIMETER FETCH OPERATIONS.
03400	
03500	1.	E ← ECW(E,Q);
03600	2.	E ← ECCW(E,Q);
03700	3.	F ← FCW(E,V);
03800	4.	F ← FCCW(E,V);
03900	5.	V ← VCW(E,F);
04000	6.	V ← VCCW(E,F);
04100	7.	Q ← OTHER(E,Q);
04200	
04300	
04400	   PARTS TREE OPERATIONS.
04500	
04600	1.	B ← PART(B);	B ← COPART(B);
04700	2.	B ← BODY(Q);	B ← SUPART(B);
04800	3.	ATT(B1,B2);	ATTACH(B1,B2);
04900	4.	DET(B);		DETACH(B);
     

00100	II. B. The Winged Edge Operations.
00200	
00300	Dynamic Storage Allocation.
00400	
00500		At the very bottom, of what is becoming a rather deep nest of
00600	primitives  within primitives, are the two dynamic storage allocation
00700	functions GETBLK and RELBLK. GETBLK allocates from 1 to 4K  words  of
00800	memory space in a contiguous block and returns the machine address of
00900	the first word of that block. RELBLK releases the indicated block  to
01000	the  available free memory space. (It is sad that the machines of our
01100	day do not come with dynamic free storage).   A  good  reference  for
01200	implementing  such  dynamic  storage,  mentioned  earlier,  is  Knuth
01300	[reference 7].  Although a fixed block size of ten or fewer words can
01400	be  made  to  handle the BFEV entities, grandiose and fickle research
01500	applications  (as  well  as  memory  use  optimization)  demand   the
01600	flexibility of a variable block size.
01700	
01800	BFEV Make & Kill Operations.
01900	
02000		Just  above  the  free storage routines are the four pairs of
02100	make and kill operations. The MKB operation creates a body block  and
02200	attaches it  as  a sub-part of the given body.  The world body always
02300	exists so that MKB(WORLD) will make a body attached to the world.  In
02400	this  paper,  the  terms `attach' and `detach' refer to operations on
02500	the parts-tree linkages.   The FEV make operations:   MKF,  MKE,  MKV
02600	create  the  corresponding  FEV  entities  and  place  them  in their
02700	respective  FEV  rings  of  the  given  body.       In  the   current
02800	implementation,  the  FEV makers set the type bits of the entity, and
02900	increment the proper total FEV counter, as well as  the  proper  body
03000	FEV  counter  in  the  given  body's node, (the Fcnt, Ecnt, Vcnt node
03100	positions are shown in figure 2.3).  The kill operations:  KLB,  KLF,
03200	KLE,  and KLV; delete the entity from its ring (or remove it from the
03300	parts-tree), release its space by calling RELBLK, and then  decrement
03400	the  appropriate  counters.   The body of the entity is needed by the
03500	kill primitives and can be provide directly  as  an  argument  or  if
03600	missing, will be found in the data by the primitive itself.
03700	
03800	Fetch Link and Store Link Operations.
03900	
04000		Each of the fetch link and store link operations named in the
04100	summary  is  a  single  machine   instruction   that   accesses   the
04200	corresponding  link position in a node.   Once BFEV nodes exist, with
04300	their rings and parts-tree already in place; the fetch and store link
04400	operations are used to construct or modify a polyhedron's surface. At
04500	this lowest level, constructing a polyhedron  requires  three  steps:
04600	first  the two vertex and two face pointers are placed into each edge
04700	in counter clockwise order as they appear when that  edge  is  viewed
04800	from  the  exterior of the solid; second an edge pointer is placed in
04900	each face and vertex, so that one can later get from a given face  or
05000	vertex  to  one  of its edges; and third the edge wings are linked so
05100	that all the ordered perimeter accessing operations  described  below
05200	will work. Wing linking is facilitated by the WING operation.
     

00100	FIGURE 2.4  -  MIDPOINT EXAMPLE (see text on page 20).
00200	
00300	                 \  pvt  /
00400	                  \     /
00500	            nccw   \   /   pcw
00600	                    \ /
00700	                  V  ⊗
00800	                     |
00900	                ENEW |
01000	                     | nvt
01100	                VNEW ⊗
01200	                     | pvt
01300	                   E |
01400	                     |
01500	                     ⊗
01600	                    / \
01700	             ncw   /   \   pccw
01800	                  /     \
01900	                 /  nvt  \
02000	
02100	INTEGER PROCEDURE MIDPOINT (INTEGER E);
02200	BEGIN "MIDPOINT"
02300		INTEGER B,ENEW,VNEW,V1,V2;
02400	
02500	α CREATE A NEW EDGE AND VERTEX;
02600		B ← BODY(E);
02700		VNEW ← MKV(B);
02800		ENEW ← MKE(B);
02900	
03000	α GET VERTICES AND FACES CONNECTED TO EDGES;
03100		PVT.(PVT(E),ENEW);
03200		PVT.(VNEW,E);
03300		NVT.(VNEW,ENEW);
03400		PFACE.(PFACE(E),ENEW);
03500		NFACE.(NFACE(E),ENEW);
03600	
03700	α GET EDGES CONNECTED TO VERTICES;
03800		IF PED(V)=E THEN PED.(ENEW,V);
03900		PED.(ENEW,VNEW);
04000	
04100	α LINK THE WINGS TOGETHER;
04200		WING(NCCW(E),ENEW);WING(PCW(E),ENEW);
04300		NCW.(E,ENEW);PCCW.(E,ENEW);
04400		PCW.(ENEW,E);NCCW.(ENEW,E);
04500	
04600	α PLACE VNEW AT MIDPOINT POSITION;
04700		V1 ← PVT(ENEW); V2 ← NVT(E);
04800		XWC(VNEW) ← (XWC(V1)+XWC(V2)) * 0.5;
04900		YWC(VNEW) ← (YWC(V1)+YWC(V2)) * 0.5;
05000		ZWC(VNEW) ← (ZWC(V1)+ZWC(V2)) * 0.5;
05100		RETURN(VNEW);
05200	END "MIDPOINT";
     

00100	The Wing Link Operation.
00200	
00300		The  WING  operation  stores edge pointers into edges so that
00400	the face perimeters and vertex  perimeters  are  made;  and  so  that
00500	surface  parity is preserved. Given two edges which have a vertex and
00600	a face in common, the WING operation places the  first  edge  in  the
00700	proper  relationship  (PCW,  NCCW,  NCW, or PCCW) with respect to the
00800	second, and the second in the proper relationship with respect to the
00900	first.  The  INVERT operation swaps the vertex, face, clockwise wing,
01000	and counter clockwise wing pointers  of  an  edge.  INVERT  preserves
01100	surface parity, but flips edge parity.
01200	
01300	The Midpoint Example.
01400	
01500		In  figure  2.4 an example of how the operations given so far
01600	could be used to code a midpoint  primitive  is  shown.  The  example
01700	midpoint  primitive  takes  an  edge argument and splits it in two by
01800	making a new edge and a new vertex  and  by  placing  them  into  the
01900	polyhedron  with the topology shown in the diagram. Then the midpoint
02000	locus is computed and the new vertex is return.  The  ALGOL  notation
02100	used  is  SAIL,  which allows defining the character "α" as a COMMENT
02200	delimiter and allows defining XWC as a real number from  the  special
02300	array  named  MEMORY.  The  MEMORY  array in SAIL is the job's actual
02400	machine memory space and gives the user the freedom of accessing  any
02500	word in his core image.
02600	
02700	The Parts-Tree Operations.
02800	
02900		As  shown  in  figure  2.1, each body node has two parts-tree
03000	links named PART and COPART. The PART link is the head of a  list  of
03100	sub-parts  of the body. When a body has no sub-parts the PART link is
03200	the negative of that body's pointer;  that  is  the  body  points  at
03300	itself.   When a body has parts, the first part is pointed at by PART
03400	and the second is pointed at by the COPART link of the first  and  so
03500	on  until  a negative pointer is retrieved which indicates the end of
03600	the parts list. The negative pointer at  the  end  of  a  parts  list
03700	points  back to the orginal body, which is the supra-part or "supart"
03800	of all those bodies in that list.
03900	
04000		The parts may be accessed by its link names PART and  COPART.
04100	Also  the  SUPART  of  a  body  returns the (positive) pointer to the
04200	supart of a body. The BODY operation returns the body to which a face
04300	edge  or  vertex  belongs;  this might be found by CDR'ing a FEV ring
04400	until a body node is reached, but for the sake of speed each edge (as
04500	shown  in  figure 2.3) has a PBODY link which points back to the body
04600	to which the edge belongs, and since each face and vertex  points  at
04700	an  edge, the body of an FEV entity can be retrieved by fetching only
04800	one or two links.
     

00100	Part Tree Operations (continued).
00200	
00300		The parts-tree is  altered  by  the  DET(B)  operation  which
00400	removes  a body B from its supart and leaves it hanging free; and the
00500	ATT(B1,B2) operation which places a free body B1 into the parts  list
00600	of  a  body  B2. Since bodies are made attached to the world body and
00700	generally  kept  attached  to  something,  two   further   parts-tree
00800	operations  are  provided, compounding the first two in the necessary
00900	manner.  The DETACH(B) operation DET's B from its current  owner  and
01000	ATT's  it  to  the world; and the ATTACH(B1,B2) operation will DET B1
01100	from its supart and attach it to a new supart.  In normal (one world)
01200	circumstances one only needs to use ATTACH to build things.
01300	
01400	Perimeter Fetch and Store Operations.
01500	
01600		There are seven perimeter fetch primitives, which when  given
01700	an  edge  and  one  of its links will fetch another link in a certain
01800	fashion.   Using the winged edge data structure these primitives  are
01900	easily implemented  in a few machine instructions which test the type
02000	bits and typically do one or  two  compares.  Clockwise  and  counter
02100	clockwise  are  always  determined  from  the outside of a polyhedron
02200	looking down on a particular face, edge or vertex.  I  apologize  for
02300	the  high redundancy on the next page, but felt that it was necessary
02400	to make the explanations independent for reference.
02500	
02600	
02700	FIGURE 2.5 - Face Perimeter Accessing with respect to edge E.
02800	
02900		      VCCW(E,F) ⊗-------E-------⊗  VCW(E,F)
03000		                 \             /
03100		                  \     F     /
03200		              ECCW(E,F)   ECW(E,F)  
03300		                    \       /
03400		                     \     /
03500		                      \   /
03600				       \ /
03700				        ⊗
03800	
03900	
04000	FIGURE 2.6 - Vertex Perimeter Accessing with respect to edge E.
04100	
04200					E
04300					|
04400			          	|          
04500			    FCCW(E,V)	|     FCW(E,V)
04600					⊗ V
04700			               / \
04800			              /   \
04900			             /     \
05000			            /       \
05100			    ECCW(E,V)       ECW(E,V)
     

00100	The Perimeter Fetch Operations.
00200	
00300	
00400	E ← ECW(E,F); Get Edge Clockwise from E about F's perimeter.
00500	E ← ECCW(E,F); Get Edge Counter Clockwise from E about F's perimeter.
00600	
00700		Given an edge and a face belonging  to  that  edge,  the  ECW
00800	fetch  primitive  returns  the  next  edge clockwise belonging to the
00900	given face's perimeter and the ECCW fetch primitive returns the  next
01000	edge counter clockwise belonging to the given face's perimeter.
01100	
01200	E ← ECW(E,V); Get Edge Clockwise from E about V's perimeter.
01300	E ← ECCW(E,V); Get Edge Counter Clockwise from E about V's perimeter.
01400	
01500		Given an edge and a vertex belonging to that  edge,  the  ECW
01600	fetch  primitive  returns  the  next  edge clockwise belonging to the
01700	given vertex's perimeter and the ECCW  fetch  primitive  returns  the
01800	next   edge   counter  clockwise  belonging  to  the  given  vertex's
01900	perimeter.
02000	
02100	F ← FCW(E,V); Get the face clockwise from E about V.
02200	F ← FCCW(E,V); Get the face counter clockwise from E about V.
02300	
02400		Given  an  edge  and a vertex belonging to that edge, the FCW
02500	fetch primitive returns the face clockwise from the given edge  about
02600	the  given  vertex  and  the  FCCW  fetch  primitive returns the face
02700	counter clockwise from the given edge about the given vertex.
02800	
02900	V ← VCW(E,F); Get the vertex clockwise from E about F.
03000	V ← VCCW(E,F); Get the vertex counter clockwise from E about F.
03100	
03200		Given  an  edge  and  a  face belonging to that edge, the VCW
03300	fetch primitive returns the vertex  clockwise  from  the  given  edge
03400	about  the given face and the VCCW fetch primitive returns the vertex
03500	counter clockwise from the given edge about the given face.
03600	
03700	F ← OTHER(E,F); Get the other face of an edge.
03800	V ← OTHER(E,V); Get the other vertex of an edge.
03900	
04000		Given  an  edge  and  one  face of that edge the OTHER fetch
04100	primitive returns the other face belonging to  that  edge.  Given  an
04200	edge  and  one  vertex of that edge the OTHER fetch primitive returns
04300	the other vertex belonging to that edge.
     

00100	(blank page)
     

00100	II. C. Elaborations on Winged Edge Structure.
00200	
00300			In  this section, some variations on the basic winged
00400	edge structure are given.   These variations arise as adaptations for
00500	my  application, and as unimplemented ideas for improvements.     The
00600	adaptations, shown in figure 2.3, include adding serial  numbers  and
00700	ALT  links  to all the faces, edges and vertices.  The serial numbers
00800	provide another way of addressing and are  especially  useful  during
00900	input and output. The ALT link is used for pointing to additional but
01000	temporary data; the most elaborate ALT data  has  to  do  with  edges
01100	during  a hidden line elimination. Sacrificing memory space for speed
01200	and flexibility, the face and edge coefficients are  stored  in  each
01300	node,  and the image coordinate (Xpp,Ypp,Zpp) and display coordinates
01400	(Xdc,Ydc) are added to each vertex. In elaborate systems,  the  image
01500	coordinates  model  a  camera  and  the  display coordinates refer to
01600	location  on  a  display  console.    Having  two  tiers   of   image
01700	coordinates allows scrolling about the modeled image without changing
01800	the camera (or  heaven  forbidden,  having  to  redo  a  hidden  line
01900	elimination).   The remaining so far unmentioned names include:   the
02000	Tjoint  link  in  vertices  which  is  for  shadow  and  hidden  line
02100	operations, the the QQ word in faces which contains photometric data,
02200	and the LOCOR and PNAME links of  a  body  node,  which  point  to  a
02300	location-orientation matrix and an ASCII print name respectively.
02400	
02500		Sacrificing  speed  for  the  sake  of  memory, the effect of
02600	having most of the extra data mentioned  above  can  be  achieved  by
02700	recomputing  it rather than fetching it. Furthermore, the winged data
02800	structure can be made slightly smaller by eliminating  the  face  and
02900	vertex  rings. Face and vertex sequential accessing can still be done
03000	by having two marking bits in each face and vertex,and by then  going
03100	thru  the edge ring looking at the two faces and two vertices of each
03200	edge for ones that are not freshly marked. It would be nice  if  such
03300	economizing could be done below the level of the operations.
03400	
03500		Besides optimizations, the next improvement idea I would like
03600	to attempt would be to split the  notion  of  a  body  into  the  two
03700	notions  of  a  "part" and a "cell".  Parts would have the parts tree
03800	and names that bodies now have, whereas a cell would have volume  and
03900	face  structure. In this hypothetical Cell, Face, Edge, Vertex (CFEV)
04000	model, each face could point to a cell on either side of it, the cell
04100	with  the  lower  serial  number  (or  something)  being construed as
04200	exterior.  Cell number zero would be the infinite void of three space
04300	in  which  everything  is embedded. The trouble with CFEV is that the
04400	important matter of a polyhedron surface has to be salvaged;  it  can
04500	not be abandoned, because models without good surface representations
04600	can not predict appearance, which is one of my requirements.
     

     

00100	SUMMARY OF POLYHEDRON PRIMITIVES.
00200	
00300	A. EULER PRIMITIVES.
00400		
00500	     1. BNEW ← MKBFV;		make a body, face & vertex.
00600	     2. KLBFEV(Q);		kill a body & all its pieces.
00700	     3.	VNEW ← MKEV(F,V);	make edge & vertex.
00800	     4.	ENEW ← MKFE(V1,F,V2);	make face & edge.
00900	     5.	VNEW ← ESPLIT(E);	split an edge.
01000	     6.	F    ← KLFE(ENEW);	kill face  &  edge leaving a face.
01100	     7.	E    ← KLEV(VNEW);	kill edge & vertex leaving an edge.
01200	     8.	V    ← KLVE(ENEW);	kill vertex & edge leaving a vertex.
01300	     9.	B    ← GLUE(F1,F2);	glue two faces together.
01400	*   10.	BNEW ← UNGLUE(E);	unglue along a seam containing E.
01500	
01600	B. SOLID PRIMITIVES.
01700	
01800	     1.	VPEAK ← PYRAMID(F); 	form a pyramid on a face.
01900	     2.	F ← PRISM(F);		form a rectangular prism.
02000	     3.	F ← CWPRISMOID(F)	form a clockwise prismoid.
02100	     4.	F ← CCWPRISMOID(F);	form a counter clockwise prismoid.
02200	     5.	ROTCOM(F);		complete a solid of rotation.
02300	     6.	FVDUAL(B);		form face vertex dual of a body.
02400	     7. BNEW ← MKCOPY(B);	make a copy of a body.
02500	     8.	EVERT(B);		turn a body surface inside out.
02600	     9.	B1 ← BUN(B1,B2);	form union of body interiors.
02700	    10.	B1 ← BIN(B1,B2);	form intersection of body interiors.
02800	
02900	C. GEOMETRIC PRIMITIVES.
03000	
03100	     1.	TRANSLATE(Q,R);
03200	     2.	ROTATE(Q,R);
03300	     3.	DILATE(Q,R);
03400	     4.	REFLECT(Q,R);
03500	
03600	D. IMAGE PRIMITIVES.
03700	
03800	     1.	PROJECTOR(CAMERA,WORLD);
03900	     2.	ELIST←CLIPER(WINDOW,WORLD);
04000	     3.	OCCULT(WORLD);
04100	*    4.	SHADOW(SUN,WORLD);
04200	*    5.	TV ← MKVID(WINDOW,WORLD);
04300	*    6.	B2D ← MKB2D(WINDOW,WORLD);
04400	*    7.	B2D ← CAREYE(TV);
04500	
04600	* under construction, Oct 1972.
     

00100	III. PRIMITIVES ON POLYHEDRA.
00200	
00300		In this section a number of primitives for  doing  things  to
00400	polyhedra  are  explained.    Although these primitives are currently
00500	implemented using the winged edge data structure, they do not require
00600	a  particular  polyhedron  representation.     Indeed,  many of these
00700	primitives  were  originally  implemented  in   a   LEAP   polyhedron
00800	representation  very  similar  to  that  of  Falk,  Feldman  and Paul
00900	[reference 5].   Thus, the primitives of this section are on a  level
01000	logically independent from the operations of the previous section.
01100	
01200		Another  aspect  of these primitives is that they can be used
01300	as the basis of a "graphics language" or more accurately as a package
01400	of  subroutines  for geometric modeling. In this vein, the primitives
01500	are currently collected as a  package  called  GEOMES  for  Geometric
01600	Modeling Embedded in SAIL; and as GEOMEL, Geometric Modeling Embedded
01700	in LISP.  A third language, called GEOMED, arises out of the  command
01800	language of a geometric model editor based on the primitives.
01900	
02000		The primitives are shown in four groups in the summary.   The
02100	first  group,  the Euler Primitives, were inspired by Coxeter's proof
02200	of Euler's formula, section 10.3 of [reference 2]. Although the proof
02300	only  required three primitives, additional ones of the same ilk were
02400	developed for convenience.   The second group  is  composed  of  some
02500	polyhedron primitives that were coded using the Euler primitives. The
02600	third group is for primitives that  move  bodies,  faces,  edges  and
02700	vertices; or compute geometric values such as length and volume. This
02800	group is underdeveloped for two reasons:  one, because  I  have  done
02900	these  computations  ad  hoc to date; and two, because they imply the
03000	subject of animation which is large and difficult and not of  central
03100	importance to vision. With the exception of the camera, my worlds are
03200	nearly (but not absolutely) static.  A  less  impoverished  geometric
03300	group  will  be  presented  in the future. The final group, has three
03400	well  developed  primitives  for  making  2D  images;   and   several
03500	primitives  that when finished will realize part of the vision system
03600	that I am trying to build.
     

00100	III. A. Euler Primitives.
00200	
00300		As mention above, the Euler primitives are based on the Euler
00400	Equation F-E+V = 2*B-2*H; where F, E, V, B and H stand for the number
00500	of faces, edges, vertices, bodies and handles that exist.   The  term
00600	"handle"  comes from topology, and is the number of well formed holes
00700	in a surface; a sphere has no handles, a torus has one handle, and an
00800	IBM  flowcharting  template  has  26  handles.     The Euler equation
00900	restricts  the  possible  topologies  of  FEV  graphs  that  can   be
01000	polyhedra;  although  such  Eulerian  polyhedra  do  not  necessarily
01100	correspond to what we normally call  a  solid  classical  polyhedron.
01200	Strict  adherence  to  constructing a polyhedron that satisfies Euler
01300	equation F-E+V = 2*B - 2*H would require only four primitives:
01400	
01500					   	+F -E +V = 2*B - 2*H
01600	
01700	   1.	Make Body, Face and Vertex	+1....+1....+1......
01800	   2.	Make Edge and Vertex.		...-1 +1............
01900	   3.	Make Face and Edge.		+1 -1...............
02000	   4.	Glue two faces of one body.	-2 +N -N..........+1
02100	   4.'	Glue two faces of two bodies.   -2 +N -N....-1......
02200	
02300	However, the  four  corresponding  destructive  primitives  are  also
02400	possible and desirable:
02500					   	+F -E +V = 2*B - 2*H
02600	
02700	   1.	Kill Body, Face and Vertex	-1....-1....-1......
02800	   2.	Kill Edge and Vertex.		...+1 -1............
02900	   3.	Kill Face and Edge.		-1 +1...............
03000	   4.	Unglue along a seam.	 	+2 -N +N..........-1
03100	   4.'	Unglue along a seam.	 	-2 +N -N....+1......
03200	
03300	And finally the operation of splitting an edge at a midpoint into two
03400	edges became so important in  forming  T-joints  during  hidden  line
03500	elimination  that the ESPLIT primitive was introduced in place of the
03600	equivalent KLFE, MKEV, MKFE sequence.
03700	
03800		In  using  the Euler primitives, some non-classical polyhedra
03900	are tolerated as  transitional  states  of  the  construction;  these
04000	transitional states are called:
04100	
04200		Seminal Polyhedron.
04300		Wire Polyhedron.
04400		Lamina Polyhedron.
04500		Shell Polyhedron.
04600		Face with Wire Spurs on its perimeter.
04700	
04800	A seminal polyhedron is like a point; a  wire  polyhedron  is  linear
04900	with two ends like a single piece of wire; lamina and shell polyhedra
05000	are surfaces, and the picturesque phrase about spurs is a restriction
05100	on  how  faces  are  dissected  into more faces.  These terms will be
05200	explained in more detail when they are needed.
     

00100	III. A. Euler Primitives.
00200	
00300	
00400	1. BNEW ← MKBFV;	Make Seminal Body.
00500	
00600		The  MKBFV  primitive  returns  a  body with one face and one
00700	vertex and no edges. Other bodies are formed by  applying  primitives
00800	to  the seminal MKBFV body. The seminal body is initially attached as
00900	a part of the world.
01000	
01100	
01200	2. KLBFEV(BNEW);	Kill Body and all its pieces.
01300	
01400		The  KLBFEV  primitive will detach and delete from memory the
01500	body given as an argument as well as all its faces,  edges,  vertices
01600	and sub-parts.
01700	
01800	
01900	3. VNEW ← MKEV(F,V);	Make an edge and a vertex.
02000	
02100		The MKEV primitive takes a face, F, and a vertex, V,  of  F's
02200	perimeter  and  it  creates a new edge, ENEW, and a new vertex, VNEW.
02300	ENEW and VNEW are called a "wire spur" at V on F.  MKEV  returns  the
02400	newly  made  vertex,  VNEW;  ENEW  can  be reached since PED(VNEW) is
02500	always ENEW. Only one wire spur is allowed at V on F at a time.
02600	
02700		When applied to the face of a seminal body,  MKEV  forms  the
02800	special  polyhedron called a "wire" and returns the new vertex as the
02900	"negative" end of the wire.  A  wire  polyhedron  is  illustrated  in
03000	figure  3.1. When applied to the negative end of a wire, MKEV extends
03100	the wire; however if applied to any other vertex  of  the  wire, MKEV
03200	refuses to change anything and merely returns its vertex argument.
03300	
03400	 Figure 3.1 - A Wire Polyhedron.      Figure 3.2  -  VNEW←MKEV(F,V);
03500	
03600	    seminal vertex ⊗ V1                          +V
03700	    positive end  +|  of wire.                   /|\
03800	                   | E1                         / |←←←←ENEW spur.
03900	                  -|                           /  |  \
04000	                   ⊗ V2                       / -VNEW \
04100	                  +|                         /         \
04200	                   | E2                     /     F     \
04300	   negative end   -| of wirer              /             \
04400	   latest vertex   ⊗ V3                   ⊗---------------⊗
     

00100	FIGURE 3.4  -  TWO EXAMPLES USING EULER PRIMITIVES. (see page 30).
00200	
00300	α MAKE A CUBE;
00400	INTEGER PROCEDURE MKCUBE;
00500	BEGIN "MKCUBE"
00600		INTEGER B,F,E,V1,V2,V3,V4;
00700	α CREATE SEMINAL POLYHEDRON;
00800		B ← MKBFV;	F ← PFACE(B);	V1 ← PVT(B);
00900		XWC(V1)←+1;	YWC(V1)←+1;	ZWC(V1)←-1;
01000	α MAKE SEMINAL POLYHEDRON INTO A LAMINA POLYHEDRON;
01100		V2 ← MKEV(F,V1);	XWC(V2)←-1;
01200		V3 ← MKEV(F,V2);	YWC(V3)←-1;
01300		V4 ← MKEV(F,V3);	XWC(V4)←+1;
01400		F  ← MKFE(V1,F,V4);
01500	α MAKE FOUR SPURS ON THE LAMINA;
01600		V1 ← MKEV(F,V1);	ZWC(V1)←+1;
01700		V2 ← MKEV(F,V2);
01800		V3 ← MKEV(F,V3);
01900		V4 ← MKEV(F,V4);
02000	α JOIN SPURS TO FORM FINAL FACES;
02100		E  ← MKFE(V1,F,V2);
02200		E  ← MKFE(V2,F,V3);
02300		E  ← MKFE(V3,F,V4);
02400		E  ← MKFE(V4,F,V1);
02500		RETURN(B);
02600	END "MKCUBE";
02700	
02800	
02900	α FORM A PYRAMID ON A FACE;
03000	INTEGER PROCEDURE PYRAMID (INTEGER F);
03100	BEGIN	"PYRAMID"
03200		INTEGER V,V0,E,E0,PEAK,EX;
03300		REAL X,Y,Z; INTEGER I;
03400		X←Y←Z←I←0;
03500	α GET A VERTEX OF THE FACE AND MAKE A SPUR TO A PEAK;
03600		E←E0←PED(F);
03700		V0 ← VCW(E0,F);
03800		PEAK ← MKEV(F,V0);
03900	α CONNECT THE OTHER VERTICES OF THE FACE TO THE PEAK;
04000		WHILE TRUE DO 
04100		BEGIN
04200			V ← VCCW(E,F);
04300			X←X+XWC(V);	Y←Y+YWC(V);	Z←Z+ZWC(V);
04400			INCREM(I);
04500			IF V=V0 THEN DONE;
04600			E ← ECCW(E,F);
04700			EX ← MKFE(PEAK,F,V);
04800		END;
04900	α POSITION THE PEAK VERTEX AT THE CENTER OF THE FACE;
05000		XWC(PEAK)←X/I;	YWC(PEAK)←Y/I;	ZWC(PEAK)←Z/I;
05100		RETURN(PEAK);
05200	END	"PYRAMID";
     

00100	4. ENEW ← MKFE(V1,F,V2);
00200	
00300		The  MKFE primitive can be thought of as a face split.  Given
00400	a face and two of  its  vertices,  MKFE  forms  a  new  face  on  the
00500	clockwise  side  of  the  line  V1  to V2 leaving the old face on the
00600	counter clockwise side. V1 becomes the PVT of ENEW,  V2  becomes  the
00700	NVT  of  ENEW, F becomes the PFACE of ENEW and FNEW becomes the NFACE
00800	of ENEW; also ENEW becomes the PED of F and FNEW.
00900	
01000	
01100	Figure 3.3  -  MKFE and KLFE.
01200	
01300	           BEFORE MKFE             AFTER ENEW←MKFE(V1,F,V2)
01400	            ⊗       ⊗                     ⊗       ⊗             
01500	           / \     / \                   / \     / \            
01600	          /   \   /   \                 /   \   /   \           
01700	         /     \ /     \               /     \ /     \          
01800	        /       ⊗       \             /      +V1      \         
01900	       /                 \           / -FNEW  |  +F    \        
02000	      ⊗         F         ⊗         ⊗         |←←←ENEW  ⊗       
02100	       \                 /           \        |        /        
02200	        \       ⊗       /             \      -V2      /         
02300	         \     / \     /               \     / \     /          
02400	          \   /   \   /                 \   /   \   /           
02500	           \ /     \ /                   \ /     \ /            
02600	            ⊗       ⊗                     ⊗       ⊗             
02700	       AFTER F←KLFE(ENEW);               BEFORE KLFE
02800	
02900		MKFE is also used to join  the two ends of a wire  polyhedron
03000	to form a "lamina"; or the two ends of wire spurs to split a face; or
03100	an end of a wire spur and a regular perimeter vertex to split a face.
03200	A "lamina polyhedron" has only two faces and thus no volume.
03300	
03400	
03500	EULER EXAMPLES.
03600	
03700		The use of the primitives discussed so far is illustrated  by
03800	the  example  subroutines  in  figure  3.4  on page 29. The make cube
03900	subroutine starts by placing a seminal vertex at (1,1,1); Then a wire
04000	of three edges is made using the MKEV primitive. As the code implies,
04100	MKEV places its new vertex at the locus of the old one.  The ends  of
04200	the  wire  are joined with a MKFE to form a lamina polyhedron, then a
04300	spur is placed on each of the vertices of the lamina, and finally the
04400	spurs are joined.
04500	
04600		The  pyramid  example  is more realistic, since polyhedra are
04700	not generated ex nihil, but rather arise out of the  vision  routines
04800	and  the geometric editor. PYRAMID takes a face as an argument (which
04900	is assumed to have no spurs) and runs a spur from one vertex  to  the
05000	middle  of the faces, then all the remaining vertices of the face are
05100	joined to that spur to form a pyramid.
     

     

00100	III. A. Euler Primitives. (Continued).
00200	
00300	5. VNEW ← ESPLIT(E);	Edge Split.
00400	
00500		This  primitive  splits  an edge by making a new vertex and a
00600	new edge. Its implementation is very similar to the midpoint  example
00700	on page 19. ESPLIT is heavily used in the hidden line eliminator.
00800	
00900	6. F ← KLFE(ENEW);	Kill Face Edge.
01000	
01100		This primitive Kills a face and an  edge  leaving  one  face.
01200	Since  this primitive is intended to be an inverse of MKFE, the NFACE
01300	of ENEW is killed. However the NFACE and PFACE  of  an  edge  may  be
01400	swapped by using the INVERT(E) primitive. See Figure 3.3 for KLFE.
01500	
01600	7. E ← KLEV(VNEW);	Kill Edge Vertex.
01700	
01800		This primitive kills an edge and a vertex leaving  one  edge.
01900	This primitive will eliminate spurs made with MKEV and midpoints made
02000	with ESPLIT; in a pure form it would have to leave  vertices  with  a
02100	valence  greater than two untouched, however it in fact "un-pyramids"
02200	them with a series of KLFE's and then kills the remaining spur.
02300	
02400	8. V ← KLVE(ENEW);	Kill Vertex Edge.
02500	
02600		This primitive kills a vertex and an edge leaving one vertex.
02700	This primitive is the face-vertex dual of  KLFE,  namely  instead  of
02800	killing  NFACE  of  E and fixing up PFACE's perimeter, KLEV kills the
02900	NVT of E and fixes up PVT of E's perimeter.
03000	
03100	
03200	9. B ← GLUE(F1,F2);	Glue two faces.
03300	
03400		This  primitive glues two faces together forming one new body
03500	out of two old ones (the body of F1 survives) or forming a handle  on
03600	the given body. The number of edges in the two faces must be the same
03700	and their orientation should be opposite (exterior to exterior).
03800	
03900	*10. BNEW ← UNGLUE(E);	Unglue along seam.	*not implemented.
04000	
04100		This  primitive  unglues  along  the  seam  containing E. The
04200	UNGLUE primitive requires that a loop of edges be marked as a  "seam"
04300	along  which unglue will form two opposite faces.  The marks are made
04400	in the temporary type bit in the edge nodes of the  given  body.   If
04500	the  cut  forms  two  disjoint  bodies then a new body is made on the
04600	NFACE side of the original E argument.
     

00100	III. B. SOLID PRIMITIVES.
00200	
00300	1. VPEAK ← PYRAMID(F);
00400	2. F ← PRISM(F);
00500	3. F ← CWPRISMIOD(F);
00600	4. F ← CCWPRISMIOD(F);
00700	
00800		These  four  primitives  are  called  the "sweep primitives",
00900	because they form a simple polyhedron from a face in a  fashion  that
01000	appears  like sweeping the face along. The sweep primitives (with the
01100	exception of PYRAMID) do not change the location of  the  given  face
01200	but  merely  copy  its perimeter, forming new faces and edges between
01300	the old perimeter and the new perimeter.  The pyramid  primitive  has
01400	already appeared as an example on page 29.
01500	
01600		Starting with a nine sided face lamina, the rocket in  figure
01700	3.5 was formed from the bottom by sweeping two prism stages, then two
01800	counter clockwise prismoid stages, and then  two  clockwise  prismoid
01900	stages,  and finally one pyramid to form the nose cone. The fins were
02000	made by prism sweeping every third face of the first stage.
     

00100	III. B. SOLID PRIMITIVES. (continued).
00200	
00300	5. ROTCOM(F);	Rotation Completion.
00400	
00500		As illustrated in the first three frames of figure 3.7 below,
00600	wire faces can be swept to form a shell. When a wire face is swept by
00700	a  sweep  primitive (other than pyramid) it is marked as a shell face
00800	of rotation and its original perimeter count is kept for later sweeps
00900	to  refer  to.    In the third frame the shell has been positioned so
01000	that its slot can be seen. The shell face now includes all the  edges
01100	of  both  pole  caps as well as the two meridians of the slot. ROTCOM
01200	takes such a shell face and breaks it into two  polar  faces  and  as
01300	many other faces as necessary, by means of the count that was saved.
     

00100	FIGURE 3.8  -  Face Vertex Duality.
     

00100	III. B. Solid Primitives. (continued).
00200	
00300	
00400	6. FVDUAL(B);
00500	7. BNEW←MKCOPY(B);
00600	
00700		These two primitives illustrate the extremes from a class  of
00800	miscellaneous  primitives.  FVDUAL is a worthless curosity and MKCOPY
00900	is quite useful but uninteresting. FVDUAL(B) of a  body  changes  all
01000	the faces of a body into vertices and all the vertices into faces, in
01100	the winged edge data structure this merely requires computing a locus
01200	for  each face (its center), re-"typing" faces and vertices, and then
01300	swapping the face and vertex link positions in each  face,  edge  and
01400	vertex of the body.
01500	
01600		Figure   3.8   illustrates   Euclid's   construction   of   a
01700	dodecahedron from a cube. The unit cube is formed, then all its edges
01800	are  midpointed  and  translated  0.2  units  into the three pairs of
01900	parallel faces; then the midpoints are lifted 0.3 units off the plane
02000	of each face of the cube; then MKFE is applied six times to split the
02100	eight sided faces  into  five  sided  faces;  giving  a  dodecahedron
02200	(nearly  regular). Applying the FVDUAL to the dodecahedron yields the
02300	icosahedron.
02400	
02500	
02600	
     

00100	III. B. Solid Primitives. (continued).
00200	
00300	
00400	8.  EVERT(B);
00500	9.  B1←BUN(B1,B2);
00600	10. B1←BIN(B1,B2);
00700	
00800		These  three  primitives  perform  the  Boolean operations on
00900	polyhedron interior volumes. EVERT(B) turns a body inside  out,  thus
01000	changing  a cube into a room, as a solid into a bubble.  Objects with
01100	infinite "interiors" are permissible; such polyhedra  are  impossible
01200	in  many  classical  developements  of  solid Geometry which make the
01300	interior of a polyhedron to  be  the  region  of  space  with  finite
01400	volume,  by  definition.  The  body  union is BUN, which allows B1 to
01500	survive if the interiors of the bodies are not disjoint. A body  with
01600	two  disjoint  polyhedrons  is shunned. The body intersection is BIN,
01700	which allows B1 to survive if the interiors of  the  bodies  are  not
01800	disjoint.
     

00100	C. GEOMETRIC PRIMITIVES.
00200	
00300	  1. TRANSLATE(Q,R);	Q argument is a body, face, edge or vertex.
00400	  2. ROTATE(Q,R);	R argument is a transformation array with
00500	  3. DILATE(Q,R);	       respect to world coordinates.
00600	  4. REFLECT(Q,R);
00700	
00800		The four Euclidean transformations are translation, rotation,
00900	reflection  and  dilation; and as first mentioned in Klein's Erlangen
01000	Program, 1872, these four primitives form a group. The primitives may
01100	be  applied  to  bodies,  faces, edges or vertices in order to change
01200	vertex world locii. Thus a body is the set of vertices in its  vertex
01300	ring,  a face is the set of vertices on its perimeter, an edge is the
01400	two vertices which are its ends, and a single vertex is  itself;  but
01500	there  are  special  cases  having  to  do  with faces.  (In GEOMED a
01600	special counter, negative Fcnt, is maintained in wire sweep faces  in
01700	order to make solids of rotation). The second argument R is a pointer
01800	to a transformation array in world coordinates of four rows and three
01900	columns:
02000				XWC, YWC, ZWC
02100				IX,  IY,  IZ
02200				JX,  JY,  JZ
02300				KX,  KY,  KZ
02400	
02500	For translation, only the XWC, YWC and ZWC are involved and  all  the
02600	vertices are translated in the obvious fashion:
02700	
02800		X ← X + XWC;	Y ← Y + YWC;	Z ← Z + ZWC;
02900	
03000	Whereas  for  rotation  (dilation  and  reflection)   the   innermost
03100	computation applied to each vertex is:
03200	
03300		X ← X + XWC;	Y ← Y + YWC;	Z ← Z + ZWC;
03400		XX ← IX*X + IY*Y + IZ*Z;
03500		YY ← JX*X + JY*Y + JZ*Z;
03600		ZZ ← KX*X + KY*Y + KZ*Z;
03700		X ← XX - XWC;	Y ← YY - YWC;	Z ← ZZ - ZWC;
03800	
03900	At this point,I should  now  present a  few  general  primitives  for
04000	setting up such transformation arrays, but I don't have them yet. The
04100	problem  involves  selecting  frames  of  references,   strength   of
04200	transformation,  axes of transformations, origins of frames and modes
04300	such  as  absolute,  relative  or  interpolated.  At  present  in  my
04400	applications  these  matters  are  handled  ad  hoc (the most general
04500	solution being the ROTDEL and  EUCLID  subroutines  of  GEOMED).  The
04600	heart  of  deriving  a  transformation  array  is  to  get a frame of
04700	reference REF and an amount of rotation DEL and to compute the matrix
04800	product:
04900			R ← (transpose(REF)cross(DEL cross REF));
05000	
05100	For  dilation (larger or smaller) cross DEL with a non-unity diagonal
05200	matrix; for reflections flip the row signs on desired axes.
     

00100	D. IMAGE PRIMITIVES.
00200	
00300	     1.	PROJECTOR(CAMERA,WORLD);
00400	     2.	ELIST←CLIPER(WINDOW,WORLD);
00500	     3.	OCCULT(WORLD);
00600	*    4.	SHADOW(SUN,WORLD);
00700	*    5.	TV ← MKVID(WINDOW,WORLD);
00800	*    6.	B2D ← MKB2D(WINDOW,WORLD);
00900	*    7.	B2D ← CAREYE(TV);
01000	
01100	* under construction, Oct 1972.
01200	
01300		PROJECTOR computes the perspective projected locus of all the
01400	vertices in a given world from a given camera.  CLIPER  computes  the
01500	portions  of 3D lines that are visible within a given display window.
01600	OCCULT compares all the edges, faces and vertices in a  given  world;
01700	using  their current projected coordinates; faces, edges and vertices
01800	that are not visible from the implied camera's viewpoint  are  marked
01900	as  hidden;  faces, edges and vertices that are visible are marked as
02000	visible; and faces, edges and vertices that were initially  partially
02100	visible  are  broken  up  into  visible  and hidden portions. The new
02200	faces, edges and vertices introduced by OCCULT  are  marked  so  that
02300	they can be removed.
02400	
02500		The following four  primitives  are  still  being  developed.
02600	SHADOW  will literally build a world with shadows in it; shadow calls
02700	OCCULT twice, once for the SUN and once for the camera. There  is  no
02800	conceptual  difficulty  in  doing many point sources, but I shall get
02900	one source working at a time.    The  MKVID  primitive  generates  TV
03000	intensity  rasters  from  the  world model after OCCULT or SHADOW has
03100	been applied.  The MKB2D primitive generates a 2D data  structure  of
03200	regions  and  edges  (which is almost a copy of the 3D structure that
03300	has been presented, but with special  attention  paid  to  T-joints);
03400	this  B2D  data  structure  is  an  image model.  Finally, the CAREYE
03500	primitive converts TV intensity rasters into B2D image  structure.  A
03600	detailed  discription  of  these image primitives can not be given at
03700	this time (OCT 1972), because I haven't finished making them.
     

     

00100	IV. APPLICATIONS.
00200	
00300		The single application around which the geometric modeling of
00400	this paper is being built is for a computer television vision (TVV ?)
00500	system for looking at real world scenes. I believe  that  a  computer
00600	must  have  a  means  of  representing what it is intended to see and
00700	further that the representation must have (in principle)  an  inverse
00800	relation  to  a  television  image.     My  first  premise  is rarely
00900	questioned, the  second  premise  is  frequentlty  questioned.    One
01000	alternative  position  is  that so called "features" can be extracted
01100	from an image and then used by a heuristic problem solver to find  an
01200	association  between  the  perceived  features  and  previous general
01300	knowledge; it is then stated that there is no need  to  go  from  the
01400	general  knowledge  or  even from the so called image "features" back
01500	down to a television image, even just in principle. I wish  to  state
01600	the  opposite,  there is a need to go from the general representation
01700	to a television image in order to  develop  computer  vision  without
01800	having  to  solve  several other problems of Artificial Intelligence.
01900	Applications of geometric modeling other than television vision might
02000	include:  architectural drawing, computer animation, and modeling for
02100	laser, radar, and sonar image systems.
     

00100	IV. A. Modeling: GEOMED - a drawing program.
00200	
00300		GEOMED,  Geometric  Model  Editor,  is for making and editing
00400	polyhedra.  The  command  language  of  GEOMED  provides  the   Euler
00500	primitives  in  the  context  of  a  push  down stack (the PADPDL) of
00600	bodies, faces, edges and vertices. The  main  difference  between  an
00700	interactive  program and a programming language being that the former
00800	carries along a working context so that most arguments  and  data  do
00900	not have to be explicitly named.
01000	
01100		V	-	make seminal vertex body.
01200		E	-	make edge and vertex.
01300		J	-	make edge and face.
01400		G	-	glue two faces.
01500	
01600		In addition to the stack, GEOMED provides frames of reference
01700	for  the  Euclidean  transformations;  there  is  a world frame, body
01800	frames, camera frames, relative frame  and  face  frames.   Also  the
01900	strength  of  a Euclidean transformation can be halved or double, set
02000	directly or entered  numerically  in  several  kinds  of  units.  And
02100	finally  the transformation can be done once or repeatedily by keying
02200	chords of Stanford's extra shift keys named "control" and "meta" with
02300	a  ;  :  ( ) - or * character. These characters are not mnemonics but
02400	were chosen because of thier positions on the keyboard.
02500	
02600		: ;	-	transform about X-axis.
02700		( )	-	transform about Y-axis.
02800		- *	-	transform about Z-axis.
02900	
03000			no shifts     -	TRANSLATION.
03100		α   -	control       -	ROTATION.
03200		β   -	meta          -	DILATION.
03300		ε   -	meta-control  -	REFLECTION.
03400	
03500		Finally,  GEOMED  provides access to all the solid primitives
03600	and hidden line elimination,  along  with  commands  for  the  stack,
03700	input,  output,  display,  and  switch  toggling.    The commands are
03800	detailed in the operating note,  SAILON-68,  along  with  a  list  of
03900	GEOMES  and  GEOMEL  subroutines.    Two  examples  should suffice to
04000	illustrate how concise and illegible GEOMED command strings are:
04100	
04200	1.	V:)\E;E(E:J↑/*S-↑		forms a cube.
04300	2.	V:@E*E*E*E*E*E*E*J↑!
04400		\\:@S)S)S)S)S)S)S)S)G↑		forms a torus.
04500	
04600	Thus  a polyhedron can be represented in a few characters (which must
04700	be  compiled);  one  might  hope  that  such  a  "representation   by
04800	generation"  could  provide  a  link  between  semantic and geometric
04900	models. The hard direction is to get from a polyhedron model  to  the
05000	command string.
     

00100	IV. B. Graphics: OCCULT - a hidden line eliminator.
00200	
00300		OCCULT is a hidden line eliminator; it is neither  a  Watkins
00400	nor  a Warnock algorithm but is rather a throw-back to the naive idea
00500	of comparing each edge with all the other edges and  having  ways  to
00600	dampen the potentially large number of comparisons that might occur.
00700	
00800		There are three kinds of dampening in OCCULT. The first (used
00900	in other hidden eliminators) is to get rid of  the  faces  that  have
01000	their  backs  to  the camera and to consider for comparision only the
01100	edges with one potentially visible face.    These  edges  are  called
01200	"folds".  The  second  kind  of  dampening,  is  to  hide  everything
01300	connected to the hidden portion of an edge when a  fold  crossing  is
01400	discovered, this is made possible by the winged edge primitives which
01500	allow polyhedron surfaces to be easily traversed  topologically;  and
01600	by  the  Euler primitives which allows the edges to be quickly broken
01700	into visible and hidden portions without losing their  topology.  The
01800	third  kind  of dampening involves having a raster of edge buckets to
01900	localize the comparisons.
02000	
02100		The reason for doing hidden line elimination in this  fashion
02200	is  to  get  the topology of the image regions and edges in a modeled
02300	scene including the shadows. OCCULT was used  to  make  some  of  the
02400	figures  that  appeared  earlier  in  this paper; for example the arm
02500	model in figure 1.2, (which required twelve seconds of PDP-10 compute
02600	time).  A  paper  on OCCULT should be available before the end of the
02700	year, 1972.
02800	
02900	
03000	IV. C. Vision:   CAREYE - a video region-edge finder.
03100	
03200		CAREYE,  Cart  Eye,  is the oldest, most rewritten, yet least
03300	finished part of the application. At present its  best  trick  is  to
03400	take  a  Television image and convert it into video intensity contour
03500	lines similar to those discussed by Krakaur  and  Horn  (of  M.I.T.).
03600	From  VIC,  Video  Intensity  Contours,  the  image  goes through two
03700	processes: first, the  camera  locus-orientation  for  the  image  is
03800	solved  by  finding  feature points in the image that coorespond with
03900	known land mark point in the world; and second, after the  camera  is
04000	solved,the  locus  of previously unknown regions of the image must be
04100	added to the world model; the third dimension of such unknown regions
04200	being assumed to be very large, until evidence is found in succeeding
04300	images that make the region "pop out" of the  background.  These  two
04400	processes  are  called  Camera  Locus Solving and Body Locus Solving;
04500	CAMLS and BODLS; and are  the  missing  links  in  making  polyhedron
04600	models merely by looking at objects and scenes of objects.
     

00100	References:
00200	
00300	1. AGIN
00400		Representation and Description of Curved Objects
00500		Stanford Artificial Intelligence AIM-172, 1972.
00600	
00700	2. COXETER
00800		Introduction to Geometry
00900		John Wiley & Sons, Inc. New York. 1961.
01000	
01100	3. EVES
01200		A Survey of Geometry.
01300		Allyn and Bacon, Inc. Boston. 1965.
01400	
01500	4. FALK
01600		Computer Interpretation of Imperfect Line Data
01700		as a Three Dimensional Scene.
01800		Stanford Artificial Intelligence AIM-132, 1970.
01900	
02000	5. FELDMAN, FALK & PAUL
02100		Computer Representation of Simply Described Scenes.
02200		Stanford Artificial Intelligence SAILON-52, 1969.
02300	
02400	6. GUZMAN
02500		Computer Recognition of Three Dimensional Objects.
02600		Project MAC Technical Report, 1968.
02700	
02800	7. KNUTH
02900		The Art of Computer Programming.
03000		Volume 1 - Fundamental Algorithms.
03100		Chapter 2 - Information Structures.
03200		Addison-Wesley. Reading,Mass. 1968.
03300	
03400	8. ROBERTS
03500		Machine Perception of Three Dimensional Solids
03600		Lincoln Laboratory Technical Report #315, 1963.
03700	
03800	9. SOBEL
03900		Camera Models and Machine Perception.
04000		Stanford Artificial Intelligence AIM-121, 1970.